This invention pertains generally to the field of digital printing systems, and specifically to a system and process of printing or otherwise displaying complex images using adaptive techniques to compress representations of image elements.
Conventional digital printing systems receive data corresponding to text and graphics in a variety of formats. These systems process such data to create a set of dots (or "pixels") on a page, which are perceived by a human observer as an image. It is conventional for such systems to represent image information in the memory of the printing system by setting a particular bit in the memory to be on or off depending upon whether a corresponding pixel is to be displayed as black or white. This is called a "bit map" or 37 pixel map" representation. In color systems, separate memory areas correspond to component colors and a number of bits may be used to represent a single pixel. Typical computer video display systems similarly rely on pixel-based representations of images.
A conventional technique for processing images is to incorporate a microprocessor into a printing device, and to program the microprocessor to interpret commands from an attached computer in accordance with the protocols of a page description language. Such subsystems are commonly known as "interpreters", and translate the printing commands from the attached computer into commands and data more easily processed by the printing device.
In practice, it is common for interpreters to decompose high-level commands corresponding to complex images into low-level commands representing, for instance, a collection of simple components known as "graphic primitives".
Two system architectures are commonly used in the industry for further processing of the low-level commands produced by page description language interpreters. The first, known as a "frame buffer", represents every pixel on a printed page as a separate bit or, in the case of color, as a set of bits in random access memory (RAM). Under this system, any page that can be described as a map of pixels can be printed. Frame buffer systems typically must process the information to be displayed on a frame-by-frame basis in which each frame must be rasterized and the data therein sent serially to the print engine. Furthermore, a substantial amount of frame buffer RAM is required to store information for the page, even when the image to be printed is extremely simple.
The second common architecture, known as "banding", stores all of the graphic primitives to be printed on the page, such as characters, graphics, images, and the like, in one or more "display lists" stored in the RAM of the printing system. A display list is typically a temporally-ordered list of graphic primitives for one area of the page, typically a horizontal band. Each display list is rasterized in turn into one of a small number of band bit maps (or "pixel maps"), or buffers, the contents of which are sent in turn to the print engine. The band buffers are reused during the processing of all the display lists of the page. Typically, most of the rasterization into band pixel maps occurs after the print engine has started to print the page. In the typical laser printer, the engine cannot be stopped in the middle of a page, so this rasterization must be fast enough to keep up with the print engine. In banding systems, relatively little RAM is required to print simple pages, and processing of one page while another page is printing is possible. However, for very complex images the size of the lists can exceed the RAM size of a comparable frame buffer system. Sufficient RAM for handling such complex images must be provided or an error will result. The requirement of real time rasterization of bands is often difficult to achieve, and an error will result if a band fails to rasterize by the time it is called for. The addition of RAM to banding systems can allow them to be converted to frame buffer systems when required.
One contributing factor to the cost and complexity of banding systems is that display list entries can quickly accumulate to an unmanageable size, not only eliminating the primary advantage of this technique but also giving rise to the possibility that not enough RAM will be available to store all of the desired display list entries.
It would be desirable to have a system and process for storing representations of graphics primitives in a manner that does not suffer the disadvantages of known approaches.